1. Field of the Invention
The present invention is directed to a system for generating and adding shortcuts to an electronic map.
2. Description of the Related Art
The computer has revolutionized the idea of a map from an image statically depicting locations to the electronic map, which consists of geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited. For example, an electronic map of roads could include distances between elements, travel time, lot numbers, tax information, tourist information, processing time, waiting time, etc. Additionally, storing a map as one or more intelligent data files on a computer allows for unlimited software applications to manipulate that data.
One advantage of the electronic map is that it can store, determine and use costs associated with various portions of the map. A cost is a variable that can be minimized or maximized. Examples of costs include time, distance, tolls paid, ease of turning, quality of scenery, etc. Typically, costs are represented as integers. Sometimes costs can be represented as real numbers or non-standard numbers. Additional information about costs and non-standard numbers can be found in U.S. Pat. No. 5,890,081, dated Apr. 6, 1999, “Using Multiple Levels Of Costs For A Pathfinding Computation,” incorporated herein by reference.
Electronic maps can be used for pathfinding, which is a method for computing a route between an origin and a destination. Some systems compute recommended routes and guide the driver by highlighting the recommended route on a map display, or by giving turn-by-turn directions (via paper, display or audio), or both. When a pathfinding system is computing a recommended route to a destination, it does so by finding the most desirable route according to certain specified criteria. These criteria may be specified by the driver, or may be set as defaults at the time of manufacture. Often, a system will be used to find a path that minimizes (or maximizes) some cost, for example, driving time.
An electronic map that is used for pathfinding must carry information about the connectivity of a road network, that is, information about the ways in which pieces of road do or do not connect to each other, for example, where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. For an area of any significant extent, this is a very large amount of information. An electronic map includes tens or hundreds of megabytes of data. In order to hold such vast quantities of data economically and allow a user to replace maps with updated copies easily, many current pathfinding apparatus (which includes general purpose computers with pathfinding software, automotive navigation systems or other map application equipment) use CD-ROMs to store the electronic map data.
Because a pathfinding process must sort through a large volume of data, the process can be slow. One means to speed up the pathfinding process is to use priority levels. The use of priority levels also enables the pathfinding process to find a path in a manner similar to the way humans perform the pathfinding process so that the final path would be similar to a path determined by a human. Having the path similar to a human determined path makes the path more understandable and user friendly.
When manually finding a path on a paper map, a user typically identifies the origin and destination. The user will navigate through residential roads to traverse to a major road such as a collector or arterial road. The user will then navigate through major roads to find a highway. The path will continue to be determined on highways until the closest highway exit to the destination is found. At that point, the user will then navigate through major roads to get as close as possible to the destination. Finally, the user will find a path from the closest point on a major road to the destination using residential roads. Thus, the user is inherently using priority levels. That is, one priority level could be the residential roads, a second priority could be the major roads and a third priority could be the highways. At one point during the pathfinding process the user is navigating through residential roads. At a second point the user is only navigating through major roads and/or highways. At a third point the user is only navigating through highways, and so on. This process is more efficient because if the user looked through all roads at all times, there would be too much data to consider and the path is not likely to be the most efficient path.
In order to efficiently find a useful path, a pathfinding system will also use priority levels. Various pathfinding systems divide the different types of roads into different levels. Whether the system uses three levels, four levels, five levels, six levels, etc., it is not necessarily important to the present discussion. Table 1 provides an example of a system that divides the roads into six priority levels.
TABLE 1Type of RoadPriorityalley0residential1collector2arterial3less important highway4important highway5
As can be seen, Table 1 divides the different roads into six types of roads: alleys, residential roads, collector roads, arterial roads, less important highways and more important highways. Each type of road is assigned a priority. In one pathfinding system, when the system is determining a path from an origin to a destination, the system will begin by performing a pathfinding exploration from the origin and destination simultaneously, considering priority one and above roads. This pathfinding exploration will continue until promotion criteria have been met. The promotion criteria include three sets of criteria. The first criteria is a promotion threshold. The promotion threshold is a cost. When the cost of traveling from the origin to a node under consideration (or from the node to the destination) is greater than the promotion threshold, then the promotion threshold has been met. The second criteria is that a minimum number of nodes at the lower priority (or higher) must have been reached in the exploration. The third criteria is that a minimum number of nodes at the higher priority (or higher) must have been reached in the exploration. For example, when promoting from priority level one to level two, priority level one is the lower priority and priority level two is the higher priority. The promotion criteria have been met when all three criteria are satisfied.
An example of a set of promotion thresholds are depicted below in Table 2. For example, the first row lists the cost in milliseconds representing the promotion threshold for promoting the exploration from level zero (and above) to level one (and above).
TABLE 2Promotion ThresholdPriority Levels for Promotion(cost in milliseconds)0    00 to 1 10,0001 to 2 10,0002 to 3120,0003 to 4300,0004 to 5600,000
An example set of values for the second and third promotion criteria are set forth in Table 3.
TABLE 3Level forMinimum number of nodes atMinimum at higherPromotionlower priority (or higher)priority (or higher)0 to 120 11 to 220202 to 330303 to 440404 to 55025
After meeting the promotion criteria for exploring at priority level one and above, the system will continue the pathfinding process by only considering roads that are priority two and above until fulfilling second promotion criteria. After reaching the second promotion criteria, the system will continue to explore the electronic map, but only consider roads at priority level three and above until reaching third promotion criteria. After meeting the third promotion criteria, the system will continue to explore through the electronic map while only considering nodes at priority level four and above until reaching fourth promotion criteria. After fulfilling the fourth promotion criteria, the system will continue exploring the electronic map while only considering roads at priority level five.
One enhancement made to some prior art pathfinding systems that use priority levels as discussed above is to include short cuts, which speed up the pathfinding process, help create better paths and help create paths that are more like a path that would be created by a human using a paper map. Some prior art systems that make use of short cuts in electronic maps have humans manually adding short cuts to the electronic map database. This process is slow, tedious and inefficient.
Other prior art systems make use of computers to automatically generate short cuts. However, these systems have suffered because the short cuts generated by the computers have tended to include paths that are not useful to the consumer. That is, although a proper short cut meeting the requirements of the particular method is generated, there exists a better short cut or path that is more useful than the short cut generated. Many users access a pathfinding system because they want the system to determine the shortest path possible in a very small amount of time. Users are disappointed with performance of a system when a user is in a neighborhood that they are familiar with and the system determines a short cut that is longer than a short cut known by the user of the pathfinding system.
Therefore, a system is needed that can automatically add short cuts to an electronic map database such that the short cuts that are added are useful and efficient short cuts.